# -*- coding: utf-8 -*-            
# @Time : 2022/12/6 22:38
# @Author  : lining
# @FileName: 串联所有单词的子串2.py
from collections import Counter


class Solution:
    def findSubstring(self, s, words):
        res = []
        m, n, ls = len(words), len(words[0]), len(s)

        # 对i进行遍历，需要考虑为啥只是0-n-1？可以理解为枚举单词长的余
        # 举个例子，需要i取n时，已经在i=0，start=n的窗口考虑了
        for i in range(n):
            # 剩余字符串可组成的单词数量少于words数量
            if i + m * n > ls:
                break
            # 新建differ
            differ = Counter()

            # 统计当前滑窗内词频0：3，3：6，6：9
            # 获得第一个滑窗内的词频统计
            for j in range(m):
                word = s[i + j * n:i + (j + 1) * n]
                differ[word] += 1

            # 统计当前窗口内多哪些，少那些？
            for word in words:
                differ[word] -= 1
                if differ[word] == 0:
                    del differ[word]

            # 对start进行遍历，间隔step为每个单词长，这里为n  0，16，3
            for start in range(i, ls - m * n + 1, n):
                # 通过下标，直接取出接下来的单词个开头的单词进行操作
                # start==i时不需要移动，直接判断
                # start!=i时，要移动
                if start != i:
                    # 要加哪个单词，维护词频差9：12
                    word = s[start + (m - 1) * n: start + m * n]
                    differ[word] += 1
                    if differ[word] == 0:
                        del differ[word]
                    # 要减哪个单词，维护词频差
                    word = s[start - n:start]
                    differ[word] -= 1
                    if differ[word] == 0:
                        del differ[word]

                # 判断，词频差为0表示满足要求
                if len(differ) == 0:
                    res.append(start)
        return res


s = 'barfoofoobarthefoobarman'# 6,9,12
words = ["bar","foo","the"]
a = Solution().findSubstring(s, words)
print(a)
